377A - Maze - CodeForces Solution

import sys
from bisect import bisect_right, bisect_left
import os
import sys
from io import BytesIO, IOBase
from math import factorial, floor, sqrt, inf
from collections import defaultdict, deque

 
BUFSIZE = 8192
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(s[:len(s) - 1])
def invr():
    return(map(int,input().split()))
def insr2():
    s = input()
    return(s.split(" "))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i and i != 1:
                divisors.append(n // i)
    return divisors

n, m, k = inlt()
maze = []
for i in range(n):
    maze.append(list(input().strip()))

if k == 0:
    for i in range(n):
        print(''.join([x for x in maze[i]]))
    exit()

graph = defaultdict(set)

for i in range(n):
    for j in range(m):
        if maze[i][j] == '.':
            if i+1 < n:
                if maze[i+1][j] == '.':
                    graph[(i, j)].add((i+1, j))
                    graph[(i+1, j)].add((i, j))
            if j+1 < m:
                if maze[i][j+1] == '.':
                    graph[(i, j)].add((i, j+1))
                    graph[(i, j+1)].add((i, j))


def dfs(graph, vertex):
    visited = set()
    tree = []
    deq = deque([vertex])
    while deq:
        vertex = deq.pop()
        if vertex not in visited:
            visited.add(vertex)
            deq.extend(graph[vertex])
            tree.append(vertex)
    return tree

tree = dfs(graph, next(iter(graph.keys())))

c = 0
while c < k:
    element = tree.pop()
    maze[element[0]][element[1]] = 'X'
    c += 1

for i in range(n):
    print(''.join([x for x in maze[i]]))